package code;

public class WildCard {
	
	/*
	 * �ϸ��O��n*m�������ù�MLE������û������ ��leetcode������
	 */
    public boolean isMatch(String s, String p) {
    	int n=s.length();
    	int m=p.length();
    	int i,j,k;
    	StringBuilder sb=new StringBuilder();
    	for(i=0;i<m;i++)
    	{
    		if(i>0 && p.charAt(i)==p.charAt(i-1) && p.charAt(i)=='*')	
    			continue;
    		sb.append(p.charAt(i));
    	}
    	p=sb.toString();
    	m=p.length();
    	System.out.println(p);
    	if(n==0 && m==0)	return true;
    	if(n==0){
    		for(i=0;i<m;i++)
    			if(p.charAt(i)!='*') 
    				return false;
    		return true;
    	}
    	if(m==0){
    		for(i=0;i<n;i++)
    			if(s.charAt(i)!='*') 
    				return false;
    		return true;
    	}
    	boolean[][] match=new boolean[n+1][m+1];
    	boolean[] row=new boolean[n+1];
    	boolean[] col=new boolean[m+1];
    	
    	if(s.charAt(0)=='*'){
    		for(i=0;i<m+1;i++){
    			match[1][i]=true;
    			row[1]=true;
    		}
    	}
    	if(p.charAt(0)=='*'){
    		for(i=0;i<n+1;i++){
    			match[i][1]=true;
    			col[1]=true;
    		}
    	}
    	match[0][0]=true;
    	
    	for(i=0;i<n;i++){
    		for(j=0;j<m;j++){
    			if(!isWildCard(s.charAt(i))){
    				if(!isWildCard(p.charAt(j))){
    					if(s.charAt(i)==p.charAt(j))
    						match[i+1][j+1]=match[i][j];
    					else match[i+1][j+1]=false;
    				}
    				else if(p.charAt(j)=='?')
    					match[i+1][j+1]=match[i][j];
    				else{
    					//*
    					match[i+1][j+1]=col[j];
//    					for(k=0;k<=i+1;k++)
//    						if(match[k][j]){
//    							match[i+1][j+1]=true;
//    							break;
//    						}
    				}
    			}
    			else if(s.charAt(i)=='?'){
    				if(p.charAt(j)!='*')
    					match[i+1][j+1]=true;
    				else{
    					//*
    					match[i+1][j+1]=col[j];
//    					for(k=0;k<=i+1;k++)
//    						if(match[k][j]){
//    							match[i+1][j+1]=true;
//    							break;
//    						}
    				}
    			}
    			else //*
    			{
    				match[i+1][j+1]=row[i];
//					for(k=1;k<=j+1;k++)
//						if(match[i][k]){
//							match[i+1][j+1]=true;
//							break;
//						}
    			}
    				
    		}
    		if(i<n && j<m){
	    		if(match[i+1][j+1])	{
	    			row[i+1]=true;
	    			col[j+1]=true;
	    		}
    		}
    	}
//    	for(i=0;i<n+1;i++){
//    		for(j=0;j<m+1;j++){
//    			System.out.print(match[i][j]+ " ");
//    		}
//    		System.out.println();
//    	}
        return match[n][m];
    }
    
    public boolean isWildCard(char c){
    	return c=='?' || c=='*';
    }
    
    
	public static void main(String[] args){
		WildCard wc=new WildCard();
		String s="abbaaababaabbbabbbaabbaa";
		String p="b****";
		System.out.println(wc.isMatch(s, p));
	}
}
